class Solution {
public:
    unordered_map<string,map<string,int> > mp;
    bool backtrack(vector<string>& res,vector<vector<string>>& tickets){
      if(res.size() == tickets.size()+1){
        return true;
      }

      for(pair<const string,int>& target : mp[res[res.size()-1]]){
        if(target.second > 0){
          res.push_back(target.first);
          target.second--;
          if(backtrack(res,tickets) == true){
            return true;
          }
           res.pop_back();
           target.second++;
        }
      }
      return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
      mp.clear();
      vector<string> res;
      res.push_back("JFK");
      for(const vector<string>& vec : tickets){
        mp[vec[0]][vec[1]]++;
      }
      backtrack(res,tickets);
      return res;
    }
};
